package goleetcode

func cherryPickup2(grid [][]int) int {
	m , n := len(grid), len(grid[0])
	f := make([][]int, n)
	g := make([][]int, n)
	for i := range f{
		f[i] = make([]int, n)
		g[i] = make([]int, n)
		for j := range f[i] {
			f[i][j] = -1
			g[i][j] = -1
		}
	}

	f[0][n-1] = grid[0][0] + grid[0][n-1]
	for i := 1; i < m; i++ {
        for j1 := 0; j1 < n; j1++ {
            for j2 := 0; j2 < n; j2++ {
                best := -1
                for dj1 := j1 - 1; dj1 <= j1 + 1; dj1++ {
                    for dj2 := j2 - 1; dj2 <= j2 + 1; dj2++ {
                        if dj1 >= 0 && dj1 < n && dj2 >= 0 && dj2 < n && f[dj1][dj2] != -1 {
                            if j1 == j2 {
                                best = max(best, f[dj1][dj2] + grid[i][j1])
                            } else {
                                best = max(best, f[dj1][dj2] + grid[i][j1] + grid[i][j2])
                            }
                        }
                    }
                }
                g[j1][j2] = best
            }
        }
        f, g = g, f
    }
	ans := 0
    for _, row := range f {
        for _, v := range row {
            ans = max(ans, v)
        }
    }
    return ans
}